Fast Support Vector Machines Using Parallel Adaptive Shrinking on Distributed Systems

摘要

Support Vector Machines (SVM), a popular machine learning technique, has beenapplied to a wide range of domains such as science, finance, and socialnetworks for supervised learning. Whether it is identifying high-risk patientsby health-care professionals, or potential high-school students to enroll incollege by school districts, SVMs can play a major role for social good. Thispaper undertakes the challenge of designing a scalable parallel SVM trainingalgorithm for large scale systems, which includes commodity multi-coremachines, tightly connected supercomputers and cloud computing systems.Intuitive techniques for improving the time-space complexity including adaptiveelimination of samples for faster convergence and sparse format representationare proposed. Under sample elimination, several heuristics for {\em earliestpossible} to {\em lazy} elimination of non-contributing samples are proposed.In several cases, where an early sample elimination might result in a falsepositive, low overhead mechanisms for reconstruction of key data structures areproposed. The algorithm and heuristics are implemented and evaluated on variouspublicly available datasets. Empirical evaluation shows up to 26x speedimprovement on some datasets against the sequential baseline, when evaluated onmultiple compute nodes, and an improvement in execution time up to 30-60\% isreadily observed on a number of other datasets against our parallel baseline.